package com.itheima.datastructure.binarysearchtree.binarytree;

import java.util.Arrays;

/*
中序，后序遍历构造二叉树
 */
public class E10Leetcode106 {
    public TreeNode buildTree(int[] inOrder,int[] postOrder){
        if(inOrder.length==0){
            return null;
        }
        //根
        int rootValue=postOrder[postOrder.length-1];
        TreeNode root=new TreeNode(rootValue);
        //划分左右子树
        for(int i=0;i<inOrder.length;i++){
            if(inOrder[i]==rootValue){
                int[] inLeft= Arrays.copyOfRange(inOrder,0,i);
                int[] inRight=Arrays.copyOfRange(inOrder,i+1,inOrder.length);

                int[] postLeft=Arrays.copyOfRange(postOrder,0,i);
                int[] postRight=Arrays.copyOfRange(postOrder,i,postOrder.length-1);

                root.left=buildTree(inLeft,postLeft);
                root.right=buildTree(inRight,postRight);
                break;
            }
        }
        return root;
    }
}
